// NFAtoDFAConverter.java
import java.io.*;
import java.util.*;

public class NFAtoDFAConverter {

    static int nodeNum = 0;

    // 计算 NFA 状态的 ε 闭包
    public static DFAState eClosure(Set<String> nfaStates, Elem nfa) {
        DFAState eClosureState = new DFAState();
        eClosureState.nfaStates = new HashSet<>(nfaStates);

        Stack<String> stateStack = new Stack<>();

        // 初始化栈，将初始状态加入栈
        for (String nfaStateName : nfaStates) {
            stateStack.push(nfaStateName);
        }

        while (!stateStack.isEmpty()) {
            String currentState = stateStack.pop();

            // 遍历 NFA 的边
            for (int i = 0; i < nfa.edgeCount; i++) {
                Edge currentEdge = nfa.edgeSet[i];

                // 如果边的起始状态是当前状态，并且边的转换符号是 '#'，那么将目标状态加入 ε 闭包
                if (currentEdge.startName.nodeName.equals(currentState) && currentEdge.tranSymbol == '#') {
                    // 如果目标状态还不在 ε 闭包中，加入它
                    if (!eClosureState.nfaStates.contains(currentEdge.endName.nodeName)) {
                        eClosureState.nfaStates.add(currentEdge.endName.nodeName);
                        // 将目标状态加入栈以便进一步处理
                        stateStack.push(currentEdge.endName.nodeName);
                    }
                }
            }
        }

        // 为 ε 闭包分配一个唯一的名称
        for (String nfaStateName : eClosureState.nfaStates) {
            eClosureState.stateName += nfaStateName;
        }

        return eClosureState;
    }

    // Move 函数
    public static DFAState move(DFAState dfaState, char transitionSymbol, Elem nfa) {
        DFAState nextState = new DFAState();

        // 遍历 DFAState 中的每个 NFA 状态
        for (String nfaStateName : dfaState.nfaStates) {
            // 遍历 NFA 状态的边
            for (int i = 0; i < nfa.edgeCount; i++) {
                Edge currentEdge = nfa.edgeSet[i];

                // 如果边的起始状态是当前状态，且转换符号与输入符号相同，加入目标状态
                if (currentEdge.startName.nodeName.equals(nfaStateName) && currentEdge.tranSymbol == transitionSymbol && currentEdge.tranSymbol != '#') {
                    nextState.nfaStates.add(currentEdge.endName.nodeName);
                }
            }
        }

        // 为 nextState 分配一个唯一的名称
        for (String nfaStateName : nextState.nfaStates) {
            nextState.stateName += nfaStateName;
        }

        return nextState;
    }

    // 检查 DFA 状态是否在状态集合中
    public static boolean isDFAStateInVector(List<DFAState> dfaStates, DFAState targetState) {
        for (DFAState state : dfaStates) {
            if (state.stateName.equals(targetState.stateName)) {
                return true;
            }
        }
        return false;
    }

    // 检查转换边是否在边集合中
    public static boolean isTransitionInVector(DFAState dfaState, DFAState dfaNextState, char symbol, List<DFATransition> dfaTransitions) {
        for (DFATransition transition : dfaTransitions) {
            if (transition.fromState.stateName.equals(dfaState.stateName) && dfaNextState.stateName.equals(dfaNextState.stateName) && symbol == transition.transitionSymbol) {
                return true;
            }
        }
        return false;
    }

    // 从 NFA 构造 DFA
    public static void buildDFAFromNFA(Elem NFA_Elem, List<DFAState> dfaStates, List<DFATransition> dfaTransitions) {
        Set<String> nfaInitialStateSet = new HashSet<>();
        nfaInitialStateSet.add(NFA_Elem.startName.nodeName);
        DFAState dfaInitialState = eClosure(nfaInitialStateSet, NFA_Elem);
        dfaStates.add(dfaInitialState);

        // 开始构建 DFA
        for (int i = 0; i < dfaStates.size(); i++) {
            DFAState dfaState = dfaStates.get(i);
            for (int j = 0; j < NFA_Elem.edgeCount; j++) {
                char symbol = NFA_Elem.edgeSet[j].tranSymbol;
                DFAState nextState = move(dfaState, symbol, NFA_Elem);
                DFAState dfaNextState = eClosure(nextState.nfaStates, NFA_Elem);

                if (!nextState.nfaStates.isEmpty()) {
                    if (!isDFAStateInVector(dfaStates, dfaNextState)) {
                        dfaStates.add(dfaNextState);
                    }
                    if (!isTransitionInVector(dfaState, dfaNextState, symbol, dfaTransitions)) {
                        dfaTransitions.add(new DFATransition(dfaState, dfaNextState, symbol));
                    }
                }
            }
        }
    }

    // 显示 DFA 状态和转移关系
    public static void displayDFA(List<DFAState> dfaStates, List<DFATransition> dfaTransitions) {
        System.out.println("DFA States:");

        for (DFAState state : dfaStates) {
            System.out.print("State " + state.stateName + " (NFA States: ");
            for (String nfaStateName : state.nfaStates) {
                System.out.print(nfaStateName + " ");
            }
            System.out.print(")");
            if (state.stateName.equals(dfaStates.get(0).stateName)) {
                System.out.print(" (Initial State)");
            }
            if (state.stateName.equals(dfaStates.get(dfaStates.size() - 1).stateName)) {
                System.out.print(" (Final State)");
            }
            System.out.println();
        }

        System.out.println("DFA Transitions:");
        for (DFATransition transition : dfaTransitions) {
            System.out.println("State " + transition.fromState.stateName + " --(" + transition.transitionSymbol + ")--> State " + transition.toState.stateName);
        }
    }

    // 生成 DFA 的 DOT 文件
    public static void generateDotFileDFA(List<DFAState> dfaStates, List<DFATransition> dfaTransitions) {
        String fileName = "D:\\bianyi\\Regex2\\result\\dfa_graph.dot";
        try (BufferedWriter dotFile = new BufferedWriter(new FileWriter(fileName))) {
            dotFile.write("digraph DFA {\n");
            dotFile.write("  rankdir=LR;  // 横向布局\n\n");
            dotFile.write(" node [shape = circle];   // 初始状态\n\n");

            // 为最后的状态添加双圆圈形状（表示结束状态）
            dotFile.write(dfaStates.get(dfaStates.size() - 1).stateName + " [shape=doublecircle];\n");

            // 添加 DFA 状态
            for (DFAState state : dfaStates) {
                dotFile.write("  " + state.stateName);
                dotFile.write(" [label=\"State " + state.stateName);
                if (state.stateName.equals(dfaStates.get(0).stateName)) dotFile.write("\\n(startState)");
                if (state.stateName.equals(dfaStates.get(dfaStates.size() - 1).stateName)) {
                    dotFile.write("\\n(endState)");
                }
                dotFile.write("\"];\n");
            }

            dotFile.write("\n");

            // 添加 DFA 转移
            for (DFATransition transition : dfaTransitions) {
                dotFile.write("  " + transition.fromState.stateName + " -> " + transition.toState.stateName + " [label=\"" + transition.transitionSymbol + "\"];\n");
            }

            dotFile.write("}\n");

            System.out.println("DFA DOT 文件生成成功。");
        } catch (IOException e) {
            System.err.println("无法打开 DOT 文件。");
        }
        // 生成文件后立即调用 readDotFile
        readDotFile(fileName);
    }

    // 读取 DOT 文件并生成图像
    public static void readDotFile(String fileName) {
        try (BufferedReader dotFile = new BufferedReader(new FileReader(fileName))) {
            System.out.println("\n读取 DOT 文件：");
            String line;
            while ((line = dotFile.readLine()) != null) {
                System.out.println(line);  // 直接输出文件内容
            }
        } catch (IOException e) {
            System.err.println("无法读取 DOT 文件：" + fileName);
        }

        // 执行 Graphviz 命令，将 DOT 文件转为 PNG 图像
        String outputFileName = fileName.substring(0, fileName.lastIndexOf(".")) + ".png";
        String command = "dot -Tpng \"" + fileName + "\" -o \"" + outputFileName + "\"";

        System.out.println("执行命令： " + command);

        try {
            Process process = Runtime.getRuntime().exec(command);
            process.waitFor();
            System.out.println("图像生成成功：" + outputFileName);
        } catch (IOException | InterruptedException e) {
            System.err.println("生成图像失败。");
        }
    }


}
